#include <stdio.h>
#include <mem.h>
#include <conio.h>
#define MAX 100
#define FILEDL "d:\btthptu.euler.txt"

unsigned a[MAX][MAX], n, // ma tran ke cua do thi
	chuaxet[MAX],
	cycle[MAX], nc,  // chu trinh Euler
	solt,   // so thanh phan lien thong
	xp, chan, le; // dinh xuat phat, so dinh bac chan, le

void XuatMaTran(); // In ma tran ke ra man hinh
int DocFile(); // Doc du lieu tu file.
void BFS(unsigned u); // Duyet theo chieu rong
void LienThong(); // Kiem tra tinh lien thong cua do thi
void XetBac(); // Xet va in ra bac cua cac dinh
void EulerCycle(); // Tim chu trinh Euler
void InChuTrinh(); // In chu trinh Euler vua tim duoc

void main()
{
 if (DocFile())
 {
   printf("Ma tran ke cua do thi:\n");
   XuatMaTran();
   XetBac();
   if (chan == n || (chan == n -2 && le == 2))
   {
     EulerCycle();
     if (chan == n)
       printf("Chu trinh Euler:\n");
     else
       printf("Duong di Euler:\n");
     InChuTrinh();
   }
 }
} // main()

void XuatMaTran()
// In ma tran ke ra man hinh
{
 unsigned i, j;
 for(i=0; i<n; i++)
 {
   for(j=0; j<n; j++)
     printf("%5d ", a[i][j]);
   printf("\n");
 }
} // XuatMaTran()

int DocFile()
// Doc du lieu tu file.
//  1: Thanh cong - 0: That bai
{
 FILE *f;
 unsigned i, j;

 f = fopen(FILEDL, "rb");
 if (f == NULL)
 {
   printf("Doc file bi loi");
   return 0;
 }

 // Bat dau doc du lieu
 fscanf(f, "%u", &n);
 for (i=0; i<n; i++)
   for (j=0; j<n; j++)
     fscanf(f, "%u", &a[i][j]);

 fclose(f);
 return 1;
} // DocFile()

void BFS(unsigned u)
// Duyet theo chieu rong
{
 unsigned queue[MAX],dauQ=0, cuoiQ=0, // hang doi
	  v, i;

 queue[cuoiQ] = u;
 chuaxet[u] = solt; // solt: so lien thong
 while (dauQ <= cuoiQ)
 {
   v = queue[dauQ];
   dauQ++;
   for (i=0; i<n; i++) // nhung dinh co lien quan
     if ((a[v][i]>0) && (chuaxet[i]==0))
     {
       cuoiQ++;
queue[cuoiQ]=i;
chuaxet[i]=solt;
     }
 }
} // BFS()

void LienThong()
// Kiem tra tinh lien thong cua do thi
{
 unsigned i;
 memset(chuaxet, 0, sizeof(chuaxet));
 solt = 0;
 for (i=0; i<n; i++)
   if (chuaxet[i] == 0)
   {
     solt++;
     BFS(i);
   }

 printf("Ma tran ke cua do thi:\n");
 XuatMaTran();

 if (solt == 1)
  printf("\n Do thi la lien thong.\n");
 else
   printf("Do thi co %u thanh phan lien thong.\n", solt);
} // LienThong()

void XetBac()
// Xet va in ra bac cua cac dinh
{
 unsigned bac, i, j;
 xp = 0;
 chan = 0;
 le = 0;
 for (i=0; i<n; i++)
 {
   bac = 0;
   for (j=0; j<n; j++)
     if (a[i][j] > 0)
       bac++;

   printf("Dinh %u co bac %u.\n", i+1, bac);
   if (bac > 0 && bac % 2 == 0) // dinh bac chan
     chan++;
   else if (bac % 2 == 1) // dinh bac le
   {
     le++;
     xp = i;
   }
 }
} // XetBac()

void EulerCycle()
// Tim chu trinh Euler
{
 unsigned stack[MAX], cuoiS = 0, // stack trung gian
	  u, i, ke;
 nc = 0;

 // Xuat phat tu dinh 0
 stack[cuoiS++] = 0; // dua dinh 0 vao stack

 while (cuoiS > 0)
 {
   u = stack[cuoiS - 1]; // u la phan tu dau stack
   ke = 0;
   for (i=0; i<n; i++)
     if (a[u][i] > 0) // dinh u ke voi dinh i
     {
       stack[cuoiS++] = i; // dua i vao stack
       a[u][i] = a[i][u] = 0; // loai bo canh (u, i) khoi do thi
       ke = 1;
       break; // chi can lay dinh ke dau tien
     }
   if (ke == 0)
   {
     cuoiS--; // loai u ra khoi stack
     cycle[nc++] = u; // dua u vao chu trinh
   }
 }
} // EulerCycle()

void InChuTrinh()
// In chu trinh Euler vua tim duoc
{
 unsigned i;
 printf("%5u", cycle[0]+1);
 for (i=1; i<nc; i++)
   printf("->%3u", cycle[i]+1);
 printf("\n");
 getch();
} // InChuTrinh()